package com.gitee.wsl.func.filter.sample
import com.gitee.wsl.func.filter.IFilterSet
import com.gitee.wsl.lang.bits.BitSet
import com.gitee.wsl.math.Math.E
import kotlin.math.exp
import kotlin.math.ln
import kotlin.math.max
import kotlin.math.pow
import kotlin.math.round

typealias Hash64Fn<T> = (T) -> Long

open class BloomFilter3<T>(
    val bitSetSize: Int,
    private val expectedNumberOfElements: Int,// expected (maximum) number of
    val hashFn: Hash64Fn<T>,
    val bitSet: BitSet,
    actualNumberOfElements: Int,
) : IFilterSet<T> {


    // elements to be added
    private var numberOfAddedElements: Int // number of elements actually added to

    /**
     * Returns the value chosen for K.<br></br>
     * <br></br>
     * K is the optimal number of hash functions based on the size of the Bloom filter and the expected number of
     * inserted elements.
     *
     * @return optimal k.
     */
    // the Bloom filter
    val k: Int // number of hash functions

    /**
     * Constructs an empty Bloom filter. The optimal number of hash functions (k) is estimated from the total size of
     * the Bloom and the number of expected elements.
     *
     * @param bitSetSize               defines how many bits should be used in total for the filter.
     * @param expectedNumberOfElements defines the maximum number of elements the filter is expected to contain.
     */
    init {
        this.numberOfAddedElements = actualNumberOfElements
        this.k = optimalNumOfHashFunctions(expectedNumberOfElements.toLong(), bitSetSize.toLong())
    }

    constructor(bitSetSize: Int,
                expectedNumberOfElements: Int,
                hashFn: Hash64Fn<T>,
                bitSet: BitSet
    ) : this(
        bitSetSize,
        expectedNumberOfElements,
        hashFn,
        bitSet,
        0
    )

//    constructor(bitSetSize: Int, expectedNumberOfElements: Int, hashFn: HashFn<T>) : this(
//        bitSetSize,
//        expectedNumberOfElements,
//        hashFn,
//        FixedBitSet(bitSetSize)
//    )

    val expectedFpp: Double
        /**
         * Calculates the expected probability of false positives based on the number of expected filter elements and the
         * size of the Bloom filter. <br></br>
         * <br></br>
         * The value returned by this method is the *expected* rate of false positives, assuming the number of inserted
         * elements equals the number of expected elements. If the number of elements in the Bloom filter is less than the
         * expected value, the true probability of false positives will be lower.
         *
         * @return expected probability of false positives.
         */
        get() = _getFalsePositiveProbability(expectedNumberOfElements.toDouble())

    /**
     * Calculate the probability of a false positive given the specified number of inserted elements.
     *
     * @param numberOfElements number of inserted elements.
     * @return probability of a false positive.
     */
    private fun _getFalsePositiveProbability(numberOfElements: Double): Double {
        // (1 - e^(-k * n / m)) ^ k
        return (1 - exp(-k * numberOfElements / bitSetSize.toDouble())).pow(k.toDouble())
    }

    val fpp: Double
        /**
         * Get the current probability of a false positive. The probability is calculated from the size of the Bloom filter
         * and the current number of elements added to it.
         *
         * @return probability of false positives.
         */
        get() = _getFalsePositiveProbability(numberOfAddedElements.toDouble())

    /**
     * Sets all bits to false in the Bloom filter.
     */
    override fun clear() {
        bitSet.clear()
        numberOfAddedElements = 0
    }

    override fun add(elm: T) {
        addHash(calcHash(elm))
        numberOfAddedElements++
    }

    override val isEmpty: Boolean
        get() = numberOfAddedElements == 0

    fun count(): Int {
        return numberOfAddedElements
    }

    override fun filter(elm: T): Boolean {
        return containsHash(calcHash(elm))
    }

    fun calcHash(elm: T): Long {
        return hashFn.invoke(elm)
        //return hashFn.hash64(elm)
    }

    // We use the trick mentioned in "Less Hashing, Same Performance: Building a Better Bloom Filter"
    // by Kirsch et.al. From abstract 'only two hash functions are necessary to effectively
    // implement a Bloom filter without any loss in the asymptotic false positive probability'
    // Lets split up 64-bit hashcode into two 32-bit hash codes and employ the technique mentioned
    // in the above paper
    private fun containsHash(hash64: Long): Boolean {
        val hash1 = hash64.toInt()
        val hash2 = (hash64 ushr 32).toInt()

        for (i in 1..k) {
            var combinedHash = hash1 + ((i + 1) * hash2)
            // hashcode should be positive, flip all the bits if it's negative
            if (combinedHash < 0) {
                combinedHash = combinedHash.inv()
            }
            val pos = combinedHash % bitSetSize
            if (!bitSet.get(pos)) {
                return false
            }
        }
        return true
    }

    private fun addHash(hash64: Long) {
        val hash1 = hash64.toInt()
        val hash2 = (hash64 ushr 32).toInt()

        for (i in 1..k) {
            var combinedHash = hash1 + ((i + 1) * hash2)
            // hashcode should be positive, flip all the bits if it's negative
            if (combinedHash < 0) {
                combinedHash = combinedHash.inv()
            }
            val pos = combinedHash % bitSetSize
            bitSet.set(pos)
        }
    }

    companion object {
//        fun forString(inputEntries: Long, fpp: Double): BloomFilter<String> {
//            val bitSetSize: Int = optimalNumOfBits(inputEntries, fpp)
//            return BloomFilter<String>(bitSetSize, inputEntries.toInt(), HashHelper.murmur3_64_string())
//        }

        /**
         * Compute optimal bits number with given input entries and expected false positive probability.
         *
         * @param inputEntries
         * @param fpp
         * @return optimal bits number
         */
        fun optimalNumOfBits(inputEntries: Long, fpp: Double): Int {
            val numBits = (-inputEntries * ln(fpp) / (ln(2.0) * ln(2.0))).toInt()
            return numBits
        }

        /**
         * Compute the false positive probability based on given input entries and bits size. Note: this is just the math
         * expected value, you should not expect the fpp in real case would under the return value for certain.
         *
         * @param inputEntries 元素个数
         * @param bitSize      总比特数
         * @return
         */
        fun estimateFalsePositiveProbability(inputEntries: Long, bitSize: Int): Double {
            val numFunction: Int = optimalNumOfHashFunctions(inputEntries, bitSize.toLong())
            val p = E.pow(-numFunction.toDouble() * inputEntries / bitSize)
            val estimatedFPP = (1 - p).pow(numFunction.toDouble())
            return estimatedFPP
        }

        /**
         * compute the optimal hash function number with given input entries and bits size, which would make the false
         * positive probability lowest.
         *
         * @param expectEntries 期望放入的元素个数
         * @param bitSetSize    比特数
         * @return hash function number
         */
        fun optimalNumOfHashFunctions(expectEntries: Long, bitSetSize: Long): Int {
            return max(1, round(bitSetSize.toDouble() / expectEntries * ln(2.0)).toInt())
        }
    }
}
